@string{Kluwer = {{Kluwer Academic Publishers}}}
@string{AAAI = {{National Conference on Artificial Intelligence}}}
@string{ASIAN = {{Asian Computing Science Conference}}}
@STRING{LFP= {{ACM Conference on LISP and Functional Programming}}}
@STRING{POPL = {{ACM Symposium on Principles of Programming Languages}}}
@STRING{ICFP={{ACM SIGPLAN International Conference on Functional Programming}}}
@STRING{LICS={{IEEE Symposium on Logic in Computer Science}}}
@STRING{FOCS={{IEEE Symposium on Foundations of Computer Science}}}
@STRING{ILPS={{International Logic Programming Symposium}}}
@string{ICALP = {{International Conference on Automata, Languages, and Programming}}}
@STRING{ICLP={{International Conference on Logic Programming}}}
@string{AMAST = {{International Conference on Algebraic Methodology and Software Technology}}}
@STRING{CADE = {{Conference on Automated Deduction}}}
@STRING{CSLI={{CSLI Center for the Study of Language of Information}}}
@STRING{CONCUR={{International Conference on Concurrency Theory}}}
@STRING{CP = {{International Conference on Principles and Practice of
		  Constraint Programming}}}  
@STRING{CCL  = {{International Conference on Constraints in Computational Logics}}}
@STRING{PPCP={{Workshop on Principles and Practice of Constraint Programming}}}
@STRING{PLILP={{International Symposium on Programming Language Implementation and Logic Programming}}}
@STRING{TACAS={{International Conference on Tools and Algorithms for the Construction and Analysis of Systems}}}
@STRING{TACS={{Annual Symposium on Theoretical Aspects of Computer Software}}}
@STRING{TAPSOFT={{Theory and Practice of Software Development}}}   
@STRING{NACLP = {{North American Conference on Logic Programming}}}
@STRING{ACL = {{Association of Computational Linguistics}}}
@STRING{LNCS = {Lecture Notes in Computer Science}}
@STRING{LNAI = {Lecture Notes in Artificial Intelligence}}
@STRING{RTA  = {{International Conference on Rewriting Techniques and Applications}}}
@STRING{SAS={{International Static Analysis Symposium}}}

@STRING{springer = "Springer-Verlag, Berlin"}
@STRING{iee      = "IEEE Computer Society Press"}
@STRING{infcomp = {Information and Computation}}
@STRING{jlp   = "The Journal of Logic Programming"}
@STRING{jfp   = "The Journal of Functional Programming"}
@string{proc = {Proceedings of the }}
@STRING{acmpress    = "ACM Press, New York"}
@STRING{mit      = "The MIT Press"}
@STRING{mitort    = "Cambridge, MA"}
@STRING{mitpress  = mit # {, } # mitort}
@STRING{cupress  = "Cambridge University Press, Cambridge, England"}
@STRING{acmpress    = "ACM Press, New York"}
@STRING{tcs   = "Theoretical Computer Science"}
@STRING{csli     = "Center for the Study of Language and Information"}
@STRING{csliort     = "Stanford University, CA"}

@string{jolli = "Journal of Logic, Language, and Information"}
@string{CL = "Computational Linguistics"}
@string{lingphil = "Linguistics \& Philosophy"}

@Article{Gol81,
   AUTHOR =     {W.~D. Goldfarb},
   TITLE  =     {The undecidability of the second-order unification problem},
   YEAR =       {1981},
   PAGES =      {225--230},
   VOLUME =     {13},
   JOURNAL =    TCS
}

@article{Mar54,
   author = {A.A. Markov},
   journal = {Trudy Mat. Inst. Steklov},
   title = {The theory of algorithms},
   volume = {1},
   number ={42},
   year = {1954},
   note = {English Translation in Israel Program for Scientific
                  Translations, Jerusalem, 1968} 
}

@InProceedings{SchulSchmi98,
  author        = "Manfred Schmidt-Schau\ss\ and  Klaus Schulz",
  title         = "On the Exponent of Periodicity of Minimal Solutions of
Context Equations",
  booktitle     = RTA,
  editor        = "Tobias Nipkow",
  year          = 1998,
  series        = "LNCS"
}


@TechReport{Schmi94,
  author = 	 {Manfred Schmidt-Schau\ss},
  title = 	 {Unification of Stratified Second-Order Terms},
  institution =  {J. W. Goethe-Universit\"at Frankfurt, Fachbereich Informatik},
  year = 	 1994,
  number =	 {12/94},
  note =	 {\url{http://www.ki.informatik.uni-frankfurt.de/papers/D-uni-SO-9-95.ps}}
}

@MastersThesis{Hoeh97,
  author =       {H\"ohl, Claudia},
  title =        {Funktionale {I}mplementierung eines {U}nfikationsalgorithmus
f\"ur {S}tratified {S}econd-{O}rder {T}erme},
  school =       {Johann Wolfgang Goethe-Universit\"at},
  type =         {Diplomarbeit},
  address = {Frankfurt, Germany},
  year =         1997
}

@inproceedings{NiePinRuh:acl97,
   author       = {Niehren, J. and Pinkal, M. and Ruhrberg, P.},
    year         = {1997},
    title        = {A Uniform Approach to Underspecification and Parallelism},
    booktitle    = {Proceedings {ACL}'97},
    pages        = {410-417},
    address      = {Madrid},
}

@incollection{NiePinRuh:cade97,
    author       = {Niehren, J. and Pinkal, M. and Ruhrberg, P.},
    year         = {1997},
    title        = {On Equality Up-to Constraints over Finite Trees, Context Unification, and One-Step Rewriting},
    editor       = {},
    booktitle    = {Proceedings 14th {CADE}},
    pages        = {},
    address      = {Townsville},
    publisher    = {Springer-Verlag}
}


@InProceedings{EggNieRuhXu98,
  author        = {Markus Egg and Joachim Niehren and Peter Ruhrberg and Feiyu Xu},
  title         = {Constraints over Lambda-Structures
                   in Semantic Underspecification},
  booktitle     = proc #{Joint 17th COLING and 36th ACL},
  shortcut      = {{COLING/ACL'98}},
  key = {d7},
  year          = {1998},
  pages         = {353--359},
  project={C4},
  ma-key={egg@coli.uni-sb.de niehren@coli.uni-sb.de peru@coli.uni-sb.de},
  abstract={We introduce a first-order language for semantic
underspecification that we call Constraint Language for 
Lambda-Structures (CLLS). A lambda-structure can be 
considered as a lambda-term up to consistent renaming 
of bound variables (alpha-equality); 
a constraint of CLLS is an underspecified description of a 
$\lambda$-structure. CLLS solves a capturing problem 
omnipresent in underspecified scope representations. 
CLLS features constraints for dominance, 
lambda binding, parallelism, and anaphoric links. Based on 
CLLS we present a simple, integrated, and underspecified 
treatment of scope, parallelism, and anaphora.}
}


@inproceedings{GuptaLambing:98,
   author       = {Gupta, Vineet and Lamping, John},
    year         = {1998},
    title        = {Efficient Linear Logic Meaning Assembly},
    booktitle    = {Proceedings {ACL}'98},
    pages        = {},
    address      = {Montreal},
}


@inproceedings{Pinkal96,
    author       = {Pinkal, Manfred},
    year         = {1996},
    title        = {Radical Underspecification},
    booktitle    = proc#{ 10th Amsterdam Colloquium},
    pages        = {587-606}
}

@InProceedings{Pinkal:salt96,
  author = 	 {Manfred Pinkal},
  title = 	 {Vagueness, ambiguity, and underspecification},
  booktitle = 	 {Proceedings of SALT VI},
  year =	 1996,
  address =	 {Rochester}
}

@InProceedings{EggKoh:uqs97,
  author = 	 {Egg, M. and M. Kohlhase},
  title = 	 {Underspecification of quantifier scope},
  booktitle = 	 {Proceedings der 6. {F}achtagung der {S}ektion {C}omputerlinguistik der {D}GfS, Heidelberg}, 
  year =	 1997
}

@InProceedings{EggKoh:dcqs97,
  author =       {Egg, M. and M. Kohlhase},
  title =        {Dynamic control of quantifier scope},
  booktitle =    {Proceedings 11th {A}msterdam {C}olloquium},
  year =         1997
}


@InProceedings{MarHinFle83,
  author =       {Mitchell P. Marcus and Donald Hindle and Margaret M. Fleck},
  title =        {D-Theory: Talking about Talking about Trees},
  booktitle =    proc#{21st annual meeting of the }#ACL,
  pages = {129--136},
  year =         1983
}

@TechReport{Muskens98,
  Author =      {Muskens, Reinhard},
  Year =        {1998},
  Title =       {Underspecified Semantics},
  Series =      {CLAUS Report},
  Number =      {95},
  Institution = {Universit\"at des Saarlandes},
  Note =        {To appear},
  Address =     {Saarbr\"ucken}
}


@Misc{Kol97,
  title = {Ein Verfahren zur
            Kontextunifikation und seine Implementierung in Oz},
  author = {Alexander Koller},
  note = {{Fortgeschrittenenpraktikum, Fachbereich Informatik, Universit\"at des
 Saarlandes}},
  year =  {1997}
}

@InProceedings{Kol98,
  author =	 {Alexander Koller},
  title =	 {Evaluating context unification for semantic
                  underspecification},
  booktitle =	 {Proceedings of the Third ESSLLI Student Session},
  year =	 1998,
  pages =        {188--199},
  editor =       {Ivana Kruijff-Korbayov\'a},
  address =      {Saarbr\"ucken, Germany}
}

@InProceedings{Xu98,
  author = 	 {Feiyu Xu},
  title = 	 {Underspecified Treatment of Verb Phrase Ellipsis},
  booktitle = 	 {Proceedings of the Third ESSLLI Student Session},
  pages =	 {269--280},
  year =	 1998,
  editor =	 {Ivana Kruijff-Korbayov\'a},
  address =	 {Saarbr\"ucken, Germany}
}

@InProceedings{NieKol98,
  title = {{Dominance Constraints in Context Unification}},
  author = {Joachim Niehren and Alexander Koller},
  booktitle = {Proceedings of the Third Conference on Logical Aspects of Computational Linguistics (Dec. 1998)}, 
  address =	 {Grenoble},
  editor =	 {M. Moortgat},
  publisher =	 {Springer-Verlag},
  year =  2001,
  volume =	 2014,
  series  = {Lecture Note in Artificial Intelligence},

}


@InProceedings{KolNieTre98,
  title = {Dominance Constraints: Algorithms and Complexity},
  author = {Alexander Koller and Joachim Niehren and Ralf Treinen},
  booktitle = {Proceedings of the Third International Conference on Logical Aspects of
               Computational Linguistics (Dec. 1998)},
  shortcut = {{LACL'98}},
  publisher =  {Springer-Verlag},
  year =  2001,
  pages = {106-125},
  volume =  2014,
  series =  {Lecture Note in Artificial Intelligence},
  key  = {c5},
  abstract={Dominance constraints for finite tree structures are widely
used in
several areas of computational linguistics including syntax,
semantics, and discourse. In this paper, we investigate algorithmic
and complexity questions for dominance constraints and their
first-order theory. We present two NP algorithms for solving dominance
constraints, which have been implemented in the concurrent constraint
programming language Oz. The main result of this paper is that the
satisfiability problem of dominance constraints is NP-complete.
Despite this intractability result, the more sophisticated of our
algorithms performs well in an application to scope
underspecification. We also show that the existential fragment of the
first-order theory of dominance constraints is NP-complete and that
the full first-order theory has non-elementary complexity.},
  project-key={C1 C4},
  ma-key={koller@coli.uni-sb.de niehren@ps.uni-sb.de}
}

@article{BackRogVS95,
   author = {R. Backofen and J. Rogers and K. Vijay-Shanker},
   journal = jolli,
   title = {A First-order Axiomatization of the Theory of Finite Trees},
   pages = {5-39},
   volume = {4},
   year = {1995}
}

@article{RogVS94,
   author = {J. Rogers and K. Vijay-Shanker},
   journal = {Computational Intelligence},
   pages = {401--421},
   title = {Obtaining Trees from their Descriptions: An Application to
            Tree-Adjoining Grammars},
   volume = {10},
   year = {1994}
}

@article{VS92,
   author = {K. Vijay-Shanker},
   journal = CL,
   pages = {481--518},
   title = {Using Descriptions of Trees in a Tree Adjoining Grammar},
   volume = {18},
   year = {1992}
}

@article{RogVS:mst94,
   author = {J. Rogers and K. Vijay-Shanker},
   journal = {Mathematical Systems Theory},
   pages = {511-546},
   title = {Equivalence of Four Extensions of Context-free Grammars},
   volume = {27},
   year = {1994}
}

@Article{Mak77,
   Title = {The Problem of Solvability of Equations in a Free Semigroup},
   Author = {Makanin, G.S.},
   Journal = {Soviet Akad. Nauk SSSR},
   number = 2,
   volume = 223,
   year = 1977
}

@article{Pacholski,
     journal = {Journal of the {ACM}},
     title = "Complexity of Makanin's Algorithm",
     year = {1996},
     volume = {43},
     author = "Antoni Ko{\'s}cielski and Leszek Pacholski"
}


@inproceedings{Lev96,
   author = {L{\'e}vy, Jordi},
   booktitle = RTA,
   title = {Linear Second Order Unification},
   publisher = {Springer-Verlag},
   address = {},
   year = {1996}
}

@incollection{Montague74,
   author = {Montague, Richard},
   address = {New Haven},
   booktitle = {Formal Philosophy. {S}elected Papers of {R}ichard {M}ontague},
   editor = {R. Thomason},
   publisher = {Yale University Press},
   title = {The Proper Treatment of Quantification in Ordinary {E}nglish},
   year = 1974
}


@inproceedings{AlsCro92,
     author = "Alshawi, H. and Crouch, R.",
     title = "Monotonic semantic interpretation",
     booktitle = {Proc. 30th ACL},
     pages = "32-39",
     year = 1992,
}

@inproceedings{Bos96,
    author       = {Bos, Johan},
    year         = {1996},
    title        = {Predicate Logic Unplugged},
    booktitle    = {Proc. 10th Amsterdam Colloquium},
    pages        = {133--143}
}

@article{Reyle93,
     title = "Dealing with ambiguities by underspecification: 
               construction, representation, and deduction",
     journal = "Journal of Semantics",
     year = 1993,
     volume = 10,
     pages = "123-179",
     author = "Uwe Reyle"}

@InProceedings{Reyle:orwa95,
  AUTHOR = {Reyle, Uwe},
  TITLE = {On Reasoning with Ambiguities},
  YEAR = {1995},
  BOOKTITLE = {Proceedings of the European Chapter of the Association of Computational Linguistics},
  ADDRESS = {Dublin}
}

@incollection{Reyle:cldtrarwa95,
     title = "Co-indexing Labelled {DRS}s to Represent and Reason with Ambiguities",
     author = "Uwe Reyle",
     booktitle = "Semantic Ambiguity and Underspecification",
     editor = "Peters, S. and van Deemter, K.",
     year = 1995,
     address = "Stanford",
     publisher = "CSLI Publications"
}


@inproceedings{Hir82,
     title = "{VP} deletion and across the board quantifier scope",
     booktitle = "NELS 12",
     year = 1982,
     address = "Univ. of Massachusetts",
     author = "Hirschb{\"u}hler, Paul",
     editor = "Pustejovsky, J. and Sells, P."
}


@Book{polsag:hpsg94,
  author = 	 "Carl Pollard and Ivan Sag",
  title = 	 "Head-driven Phrase Structure Grammar",
  publisher = 	 "CSLI and University of Chicago Press",
  year = 	 1994
}

@Book{Cooper83,
  author = 	 "Robin Cooper",
  title = 	 "Quantification and Syntactic Theory",
  publisher = 	 "Reidel",
  address =      "Dordrecht",
  year = 	 1983
}


@Inproceedings{Kehler:93,
  author = 	 "Andrew Kehler",
  title = 	 "A Discourse Copying Algorithm for Ellipsis and Anaphora Resolution",
  booktitle = "Proceedings of EACL",
  year = 	 1993
}
		  
@PhdThesis{Kehler:icfitcodi95,
  author = 	 "Andrew Kehler",
  title = 	 "Interpreting Cohesive Forms in the Context of
		  Discourse Inference",
  school = 	 "Harvard University",
  year = 	 1995
}

@Inproceedings{HobKeh:tpce97,
  author =       "Hobbs, Jerry R and Kehler, Andrew",
  title =        "A Theory of Parallelism and the Case of {VP}-Ellipsis",
  booktitle =    proc#{ annual meeting of the }#ACL,
  address =      {Madrid},
  year =         1997,
  pages =        "394-401"
}


@Article{ShiPerDal96,
  author = 	 "Stuart Shieber and Fernando Pereira and Mary Dalrymple",
  title = 	 "Interaction of Scope and Ellipsis",
  journal =	 lingphil,
  year =	 1996,
  volume =	 19,
  pages =	 "527-552"
}


@Article{DalLamPerSar97,
  author = 	 {Mary Dalrymple and John Lamping and Fernando Pereira and Vijay Saraswat},
  title = 	 {Quantifiers, anaphora, and intensionality},
  journal = 	 {Journal of Logic, Language, and Information},
  year = 	 1997,
  volume =	 6,
  pages =	 {219-273}
}

@InCollection{Marcus87,
  author =       {Marcus, M.P.},
  title =        {Deterministic Parsing and Description Theory},
  booktitle =    {Linguistic Theory and Computer Applications},
  editor =       {Whitelock, P. and Wood, M.M. and Somers, H.L. and Johnson, R. and Bennett, P.},
  publisher =    {Academic Press},
  adress =       {London},
  year =         1987
}

@phdthesis{May:tgoq77,
    author       = {May, Robert},
    year         = {1977},
    title        = {The Grammar of Quantification},
    type         = {Doctoral Dissertation},
    school       = {MIT},
    address      = {Cambridge}
}

@InCollection{Gardent:si97,
  author =       {Claire Gardent},
  title =        {Sloppy Identity},
  booktitle =    {Logical Aspects of Computational Linguistics},
  publisher =    {Springer-Verlag},
  year =         1997
}


@InProceedings{GarKoh:hocuanls96,
  author = 	 "Claire Gardent and Michael Kohlhase",
  title = 	 "Higher-Order Coloured Unification and Natural
		  Language Semantics",
  booktitle =	 "Proceedings {ACL}'96",
  year =         1996}

@Inproceedings{GarKoh:cpid97,
  author = 	 "Claire Gardent and Michael Kohlhase",
  title = 	 "Computing parallelism in Discourse",
  booktitle =	 {Proceedings {IJCAI}'97},
  year =         1997,
  pages = "1016-1021",
}


@PhdThesis{Gardent:gveubg,
  author = 	 {Claire Gardent},
  title = 	 {Gapping and VP Ellipsis in a Unification Based Grammar},
  school = 	 {University of Edinburgh},
  year = 	 {1991}
}

@Article{GroSto91,
  author = 	 "Jeroen Groenendijk and Martin Stokhof",
  title = 	 "Dynamic Predicate Logic",
  journal =	 lingphil,
  year =	 1991,
  volume =	 14,
  pages =	 "39-100"
}



@Book{KohKus:clausdlc97,
  author = 	 "Michael Kohlhase and Susanna Kuschert",
  title = 	 "Dynamic Lambda Calculus",
  publisher   =  "{CLAUS}-Report~91, Universit{\"a}t des {S}aarlandes",
  year = 	 1997
}


@Unpublished{KohKus:dlc97,
  author = 	 {Michael Kohlhase and Susanna Kuschert},
  title = 	 {Dynamic Lambda Calculus},
  note = 	 {Presented at the Fifth Mathematics of Language (MOL5), Dagstuhl, Germany},
  year =	 1997
}


@TechReport{Gardent:phouad97,
  author = 	 "Claire Gardent",
  title = 	 "Parallelism, HOU and deaccenting",
  institution =  "University of Saarbr{\"u}cken",
  year = 	 1997,
  type =	 "CLAUS Report",
  number =	 85
}


@TechReport{Worm:Bericht,
  author = 	 "Karsten Worm",
  title = 	 "Robuste Semantische {V}erarbeitung",
  institution =  "Universit{\"a}t des Saarlandes",
  year = 	 1997,
  type =	 "Verbmobil Report",
  number =	 200,
  address =      "Saarbr{\"u}cken",
  note    = "to appear"
}

@TechReport{Smo94,
author	= "Gert Smolka",
title	= "The Definition of Kernel {O}z",
institution = {German Research Center for Artificial Intelligence (DFKI)},
address	= {Saarbr\"ucken},
type	= {DFKI Oz Documentation Series},
year	= 1994,
}



@Misc{OzWebPage,
  key = {Oz}, 
  author = {{Oz Development Team}},
  year = 1999,
  title =	 {The {M}ozart {P}rogramming {S}ystem web pages. \url{http://www.mozart-oz.org/}.}
}

@article{huet,
   author = {G\'{e}rard P. Huet},
   journal = {Theoretical Computer Science},
   pages = {27-57},
   title = {An Unification Algorithm for Typed $\lambda $-Calculus},
   volume = {1},
   year = {1975}
}

@Book{qlf,
  editor = 	 "Alshawi, H.",
  title = 	 "The {C}ore {L}anguage {E}ngine",
  publisher = 	 "MIT Press",
  address = {Cambridge/London},
  year = 	 1992
}

@incollection{EggLeb95,
   AUTHOR =  "Egg, M. and Lebeth, K.",
   TITLE =   "Semantic underspecification and modifier attachment ambiguities",
   booktitle = "Integrative Ans{\"a}tze in der Computerlinguistik ({DGfS/CL} '95)",
   EDITOR = "Kilbury, J. and Wiese, R.",
   publisher = "Seminar f{\"u}r Allgemeine Sprachwissenschaft",
   address = "D{\"u}sseldorf",
   pages  =  "19--24",
   YEAR =    1995}

@Book{KamRey93,
  author =       "Hans Kamp and Uwe Reyle",
  title =        "From Discourse to Logic",
  publisher =    "Kluwer",
  year =         1993,
  address =      "Dordrecht"
}

@TechReport{fracasD9,
author	= "{{F}ra{C}a{S} Consortium}",
title	= "The State of the Art in Computational Semantics: Evaluating the Descriptive Capabilities of Semantic Theories",
institution = {Centre for Cognitive Science},
address	= {University of Edinburgh},
type	= {FraCaS Deliverable},
key     = {{F}ra{C}a{S}},
number  = "D9",
year	= 1994,
}

@TechReport{fracasD15,
author	= "{{F}ra{C}a{S} Consortium}",
title	= "Building the Framework",
institution = {Centre for Cognitive Science},
publisher	= {University of Edinburgh},
type	= {FraCaS Deliverable},
number  = "D15",
key     = {{F}ra{C}a{S}},
year	= 1996,
}

@incollection{Eij:btf96,
key = "Eijck",
author	= "Jan van Eijck",
editor  = "{F}ra{C}a{S}-Consortium",
booktitle = "Building the Framework",
institution = {Centre for Cognitive Science},
publisher	= {University of Edinburgh},
title	= {[{C}hapter 10.2 of {F}ra{C}a{S} {R}eport {D}15]},
year	= 1996,
}

@InProceedings{BlaGarMey93,
  author = 	 "P. Blackburn and C. Gardent and W. Meyer-Viol",
  title = 	 "Talking about trees",
  BOOKTITLE = {Proceedings of the European Chapter of the Association of Computational Linguistics},
address	= {Utrecht},
  year = 	 1993
}


@Article{DalShiPer91,
  author = 	 "Mary Dalrymple and Stuart Shieber and Fernando Pereira",
  title = 	 "Ellipsis and Higher-Order Unification",
  journal =	 lingphil,
  year =	 1991,
  volume =	 14,
  pages =	 "399-452"
}


@InProceedings{Crouch95,
  AUTHOR = {Crouch, Richard},
  TITLE = {Ellipsis and Quantification: A Substitutional Approach},
  YEAR = {1995},
  BOOKTITLE = {Proceedings of the 7th {EACL}},
  ADDRESS = {Dublin},
  pages = {229--236}
}



@InProceedings{Nerbonne,
  author = 	 {John Nerbonne},
  title = 	 {Constraint-Based Semantics},
  booktitle = 	 {Proceedings 8th {A}msterdam {C}olloquium},
  pages =	 {425-444},
  year =	 1992
}


@Article{HobShi87,
  author = 	 "Hobbs, Jerry R. and Shieber, Stuart M.",
  title = 	 "An Algorithm for Generating Quantifier Scopings",
  journal =	 "Computational Linguistics",
  year =	 1987,
  volume =	 13,
  pages = 	 "47--63"
}


@Article{Alshawi90,
  author = 	 "Hiyan Alshawi",
  title = 	 "Resolving Quasi Logical Form",
  journal =	 "Computational Linguistics",
  year =	 1990,
  volume =	 16,
  pages = 	 "133-144"
}

@BOOK{DeemterPetersBook,
       AUTHOR = {Kees van Deemter and Stanley Peters},
       TITLE = {Semantic Ambiguity and Underspecification},
       PUBLISHER = {CSLI},
       ADDRESS = "Stanford",
       YEAR = {1996}}


@inproceedings{Saraswat:POPL91,
   author = {Saraswat, Vijay A. and Rinard, Martin and Panangaden, Prakash},
   booktitle = POPL,
   publisher = acmpress,
   pages = {333--352},
   title = {Semantic foundations of concurrent constraint programming},
   year = {1991}
}

@inproceedings{SmolkaGammaCalculus:94,
   author	= {Gert Smolka},
   title	= {A Foundation for Concurrent Constraint Programming},
   booktitle = {{Constraints in Computational Logics}},
   year	=  {1994},
   publisher = springer,
   annote = {M\"unchen},
   pages = {50--72}
}

@InProceedings{Smolka95, 
  author = {Gert Smolka},
  title =  {The {O}z {P}rogramming {M}odel}, 
  booktitle = {Computer Science Today},
  year =   {1995},
  publisher = springer,
  editor  = {Jan van Leeuwen},
  pages = {324--343}
} 


@Unpublished{CopFliSag97,
  author = 	 {A.~Copestake and D.~Flickinger and I.~Sag},
  title = 	 {Minimal {R}ecursion {S}emantics. {A}n {I}ntroduction},
  note = 	 {Unpublished manuscript, available at \url{http://www.cl.cam.ac.uk/~aac10/papers/newmrs.pdf}},
  address =      {CSLI, Stanford University},
  year =         {1999}
}

@Book{FieMay:iai94,
  author = 	 "Robert Fiengo and Robert May",
  title = 	 "{I}ndices and {I}dentity",
  publisher = 	 "MIT press",
  address =      "Cambridge",
  year = 	 1994
}

@PhdThesis{Sag:dalf76,
  author = 	 {Ivan Sag},
  title = 	 {Deletion and {L}ogical {F}orm},
  school = 	 {MIT},
  address =      {Cambridge},
  year = 	 {1976}
}

@Book{May:lf85,
        author = "Robert May",
        title = "Logical Form. Its structure and derivation",
        publisher = "MIT Press",
        address = "Cambridge",
        year = "1985"}

@InProceedings{MonRij98,
  author = 	 {Christof Monz and Maarten de Rijke},
  title = 	 {A Tableaux Calculus for Ambiguous Quantification},
  booktitle = 	 {Proceedings of TABLEAUX 98},
  pages =	 {232--246},
  year =	 1998,
  editor =	 {Henriette de Swart},
  number =	 1397,
  series =	 {LNAI},
  publisher =	 {Springer Verlag}
}

@InProceedings{KoeRey96,
  author = 	 {Esther K\"onig and Uwe Reyle},
  title = 	 {A general reasoning scheme for underspecified representations},
  booktitle = 	 {Logic and its applications. Festschrift for Dov Gabbay. Part I},
  year =	 1996,
  editor =	 {H. J. Ohlbach and U. Reyle},
  publisher =	 {Kluwer}
}

@InProceedings{Monz98,
  author = 	 {Christof Monz},
  title = 	 {Dynamic Semantics and Ambiguity},
  booktitle = 	 {Proceedings of the Third ESSLLI Student Session},
  pages =	 {212--222},
  year =	 1998,
  editor =	 {Ivana Kruijff-Korbayov\'a},
  address =	 {Saarbr\"ucken, Germany}
}

@InProceedings{GarWeb98,
  author = 	 {Claire Gardent and Bonnie Webber},
  title = 	 {Describing discourse semantics},
  booktitle = 	 {Proceedings of the 4th TAG+ Workshop},
  year =	 1998,
  address =	 {Philadelphia}
}

@Article{BarCoo81,
  author =       "Jon Barwise and Robin Cooper",
  title =        "Generalized Quantifiers and Natural Language",
  year =         "1981",
  journal =      "Linguistics and Philosophy",
  pages =        "159--219",
  volume =       "4",
}

@PhdThesis{Cooper75,
  author = 	 {Robin Cooper},
  title = 	 {Montague's semantic theory and transformational syntax},
  school = 	 {University of Massachusetts},
  year = 	 1975,
  address =	 {Amherst}
}

@Article{BackSmo95,
  author = 	 {R. Backofen and Gert Smolka},
  title = 	 {A complete and recursive feature theory},
  journal = 	 TCS,
  year = 	 1995,
  volume =	 146,
  pages =	 {43--268}
}

@InCollection{Deemter96,
  author = 	 {Kees van Deemter},
  title = 	 {Towards a logic of ambiguous expressions},
  booktitle = 	 {\cite{DeemterPetersBook}},
  publisher =	 {CSLI Publications},
  year =	 1996,
  address =	 {Stanford}
}

@InCollection{Doelling94,
  author = 	 {J. D\"olling},
  title = 	 {Sortale {S}elektionsbeschr\"ankungen und systematische {B}edeutungsvariation},
  booktitle = 	 {Kognitive Semantik/Cognitive Semantics},
  pages =	 {41--59},
  publisher =	 {Narr},
  year =	 1994,
  editor =	 {M. Schwarz},
  address =	 {T\"ubingen}
}

@Article{LasAsh93,
  author = 	 {Alex Lascarides and Nicholas Asher},
  title = 	 {Temporal relations, discourse relations, and commonsense entailment},
  journal = 	 lingphil,
  year = 	 1993,
  volume =	 16,
  pages =	 {437--493}
}

@InCollection{LasMahMar88,
  author = 	 {J. Lassez and M. Maher and K. Marriott},
  title = 	 {Unification revisited},
  booktitle = 	 {Foundations of Deductive Databases and Logic Programming},
  pages =	 {587--625},
  publisher =	 {???},
  year =	 1988,
  editor =	 {J. Minker}
}

@Book{Pustejovsky95,
  author =	 {James Pustejovsky},
  title = 	 {The generative lexicon},
  publisher = 	 {MIT Press},
  year = 	 1995,
  address =	 {Cambridge}
}

@TechReport{clare,
  author = 	 {H. Alshawi and D. Carter and R. Crouch and S. Pulman and M. Rayner and A. Smith},
  title = 	 {{CLARE}: A Contextual Reasoning and Cooperative Response Framework for the {C}ore {L}anguage {E}ngine},
  institution =  {SRI International},
  year = 	 1992,
  number =	 {CRC-028},
  address =	 {Cambridge, England},
  note = {\url{http://www.cam.sri.com/tr/crc028/paper.ps.Z}}
}

@InProceedings{BlaMeyRij95,
  author = 	 {Patrick Blackburn and Wilfried Meyer-Viol and Maarten de Rijke},
  title = 	 {A Proof System for Finite Trees},
  booktitle = 	 {Computer Science Logic. Selected Papers of the 9th International Workshop CSL '95 (Paderborn, Germany)},
  pages =	 {86--105},
  year =	 1995,
  editor =	 {Hans Kleine B\"uning},
  number =	 1092,
  series =	 {LNCS},
  publisher =	 springer
}

@Article{Rabin69,
  author = 	 {M. Rabin},
  title = 	 {Decidability of second-order theories and automata on infinite trees},
  journal = 	 {Transactions of the American Mathematical Society},
  year = 	 1969,
  volume =	 141,
  pages =	 {1--35}
}


@INPROCEEDINGS{duchier99:_const_based_treat_descr,
  title = {A Constraint-Based Treatment of Descriptions},
  year = 1999,
  author = {Denys Duchier and Claire Gardent},
  abstract = {Both in computational linguistics and in formal semantics, tree (or graph) descriptions stated in terms of <i>dominance</i>
 have become common.  Yet the issue of how such descriptions are
 processed has been little explored.  In this paper, we present
 a constraint-based treatment of descriptions: we develop a
 formulation in terms of sets, which is simple and declarative, and,
 at the same time, constitutes an efficient implementation.  We further
 show how the treatement of tree descriptions can be extended to
 DAG descriptions and apply it to a description-based account of
 discourse.},
  booktitle = {Third International Workshop on Computational Semantics (IWCS-3)},
  pages = {71--85},
  editor = {H.C. Bunt and E.G.C. Thijsse},
  address = {Tilburg, NL},
  ma-key = {duchier@ps.uni-sb.de claire@coli.uni-sb.de},
  sline = 3001,
  project-key = {C1 C3 C2}
}



@InCollection{DucGar99,
  author =       {Denys Duchier and Claire Gardent},
  title =        {Tree Descriptions, Constraints and Incrementality},
  booktitle =    {Computing Meaning, Volume 2},
  publisher =    {Kluwer Academic Publishers},
  year =         2001,
  editor =       {Harry Bunt and Reinhard Muskens and Elias Thijsse},
  volume =       77,
  series =       {Studies In Linguistics And Philosophy},
  pages = {205--227},
  ma-key = {duchier@ps.uni-sb.de claire@coli.uni-sb.de},
  abstract = {In \textit{A Constraint-Based Treatment
of Descriptions}, we presented a constraint-based method for
enumerating the models satisfying a given tree description and described
its application to the underspecified semantic representation of
discourse advocated by Gardent \& Webber (1998).  In this paper, we
indicate how the approach may be further extended to support discourse
level \textit{incremental} processing.

\textbf{Keywords:}
incremental processing, underspecified representations, tree descriptions,
dominance constraints, constraint programming, discourse semantics.},
}

@Article{venkatamaran87,
  author = 	 {K. N. Venkatamaran},
  title = 	 {Decidability of the purely existential fragment of the theory of term algebra},
  journal = 	 {J. ACM},
  year = 	 1987,
  volume =	 34,
  number =	 2,
  pages =	 {492--510}
}

@Misc{EggKolNieRuh98,
  author =	 {Markus Egg and Alexander Koller and Joachim Niehren and Peter Ruhrberg},
  title =	 {Constraints over Lambda Structures, Antecedent Contained Deletion, and Quantifier Identities},
  howpublished = {Submitted. \url{http://www.coli.uni-sb.de/~koller/papers/acd.html}},
  year =	 1999
}

@TechReport{Jaspars97,
  author =       {Jaspars, Jan},
  title =        {Minimal logics for reasoning with ambiguous expressions},
  institution =  {Universit\"at des Saarlandes},
  Series =       {CLAUS Report},
  year =         1997,
  number =       94,
  address =      {Saarbr\"ucken},
  note =         {\url{ftp://ftp.coli.uni-sb.de/pub/CLAUS/claus94.ps}.}
}

@InCollection{Bierwisch83,
  author = 	 {Manfred Bierwisch},
  title = 	 {Semantische und konzeptionelle {R}epr{\"a}sentation lexikalischer {E}inheiten},
  booktitle = 	 {Untersuchungen zur {S}emantik},
  pages =	 {61--99},
  publisher =	 {Akademie-Verlag},
  year =	 1983,
  editor =	 {R. Ruzicka and W. Motsch},
  address =	 {Berlin},
  annote =	 {Ruzicka hat noch jede Menge Akzente drauf}
}

@incollection{Muskens95,
author={Muskens, R.A.},
year={1995},
title={Order-Independence and Underspecification},
editor={Groenendijk, J.},
booktitle={Ellipsis,
Underspecification, Events and More in Dynamic Semantics},
publisher={{DYANA} {D}eliverable R.2.2.{C}},
}        

@PhdThesis{Rogers94,
  author = 	 {James Rogers},
  title = 	 {Studies in the Logic of Trees with Applications to Grammar Formalisms},
  school = 	 {University of Delaware},
  year = 	 1994
}

@InProceedings{MeyKem98,
  author = 	 {Wilfried Meyer-Viol and Ruth Kempson},
  title = 	 {Sequential Construction of Logical Forms},
  booktitle = 	 {Proceedings of the Third Conference on Logical
		  Aspects of Computational Linguistics},
  address =      {Grenoble, France},
  year =	 1998
}




@PhdThesis{Egg99,
  author = 	 {Markus Egg},
  title = 	 {Reinterpretation by Underspecification},
  school = 	 {University of the Saarland},
  year = 	 2000,
  type =	 {Habilitation thesis},
  note = {To appear}
}

@InProceedings{BilLan89,
  author = 	 {Sylvie Billot and Bernard Lang},
  title = 	 {The structure of shared forests in ambiguous parsing},
  booktitle = 	 {Proceedings of the 27th ACL},
  pages =        {143--151},
  year =	 1989,
  address =	 {Vancouver}
}

@InProceedings{Poesio94,
  author = 	 {Massimo Poesio},
  title = 	 {Ambiguity, Underspecification, and Discourse Interpretation},
  booktitle = 	 {Proceedings of IWCS-1},
  year =	 1994,
  address =	 {Tilburg}
}

@Article{Courcelle83,
  author = 	 {Bruno Courcelle},
  title = 	 {Fundamental properties of infinite trees},
  journal = 	 tcs,
  year = 	 1983,
  volume =	 25,
  number =	 2,
  pages =	 {95--169}
}

@InProceedings{MueMue97,
  author = 	 {Tobias M{\"u}ller and Martin M{\"u}ller},
  title = 	 {Finite set constraints in {O}z},
  booktitle = 	 {13. Workshop Logische Programmierung},
  pages =	 {104--115},
  year =	 1997,
  editor =	 {Fran\ccois Bry and Burkhard Freitag and Dietmar Seipel},
  address =	 {Technische Universit{\"a}t M{\"u}nchen}
}

@Misc{KolNie99,
  author =	 {Alexander Koller and Joachim Niehren},
  title =	 {Towards Underspecified Processing of Dynamics},
  howpublished = {Workshop on Dynamic Logic, Schloss Dagstuhl},
  year =	 1999
}

@InProceedings{Schiehlen97,
  author = 	 {Michael Schiehlen},
  title = 	 {Disambiguation of Underspecified Discourse Repesentation Structures under Anaphoric Constraints},
  booktitle = 	 {Proceedings of IWCS-2},
  year =	 1997,
  address =	 {Tilburg}
}

@MastersThesis{Koller99,
  author = 	 {Alexander Koller},
  title = 	 {Constraint Languages for Semantic Underspecification},
  school = 	 {Universit{\"a}t des Saarlandes},
  address =      {Saarbr{\"u}cken, Germany},
  year = 	 1999,
  type =	 {Diplom thesis},
  note =         {\url{http://www.coli.uni-sb.de/~koller/papers/da.html}.}
}

@InProceedings{BriCopBog:ep90,
  author = 	 {Briscoe, T. and Copestake, A. and B. Boguraev},
  title = 	 {Enjoy the paper: lexical semantics via lexicology},
  booktitle = 	 {Proceedings of the 13th International Conference on Computational Linguistics},
  year =	 1990,
  address =	 {Helsinki},
  pages =	 {42-47}}

@Article{CopBri:spse95,
  author = 	 {Copestake, A. and T. Briscoe},
  title = 	 {Semi-productive polysemy and sense extension},
  journal = 	 {Journal of Semantics},
  year = 	 1995,
  volume =	 12,
  pages =	 {15-67}
}

@Article{HobStiAppMar:iaa93,
  author = 	 {Hobbs, J. and M. Stickel and D. Appelt and P. Martin},
  title = 	 {Interpretation as abduction},
  journal = 	 {Artificial Intelligence},
  year = 	 1993,
  volume =	 63,
  pages =	 {69-142}
}

@TechReport{choli,
  author =       {R.~Debusmann and M.~Egg and A.~Koller and K.~Konrad and
                  J.~Niehren and G.~Schaefer and S.~Thater and
                  V.~Winter and F.~Xu},
  title =        {{CHOLI}: A natural language system for semantic construction
                  and evaluation},
  institution =  {Universit\"at des Saarlandes},
  year =         1998,
  type =         {{CLAUS} Report},
  address =      {Saarbr\"ucken},
                  note = {To appear.}
}

@Article{nunberg95,
  author = 	 {G. Nunberg},
  title = 	 {Transfers of Meaning},
  journal = 	 {Journal of Semantics},
  year = 	 1995,
  volume =	 12,
  pages =	 {109-132}
}

@Misc{relax2000,
author = {Alexander Koller and Joachim Niehren and Kristina 
                         Striegnitz}, 
               title  = {Relaxing Underspecified Semantic Representations for 
                         Reinterpretation}, 
               year   = 2000, 
               address = {Orlando, Florida}, 
  note          = {Journal submission available at
             \url{http://www.ps.uni-sb.de/Papers/abstracts/relax2000.html}.
             Extension on a conference paper
             that appeared at MOL'99 (
             \url{http://www.ps.uni-sb.de/Papers/abstracts/Relax99.html}).
                     Last revision: Feb 19, 2000},
}


@article{Koller:2000:RUS,
  author =  {A.~Koller and J.~Niehren and K.~Striegnitz},
  title =  {Relaxing Underspecified Semantic Representations for Reinterpretation},
  journal =  {Grammars},
  volume =  {3},
  number =  {2-3},
  url =  {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/relax2000.ps.gz},
  abstract =  {Type and sort conflicts in semantics are usually resolved by a process of reinterpretation, which introduces an operator into the semantic representation. We elaborate on the foundations of a recent approach to reinterpretation within a framework for semantic underspecification. In this approach, relaxed underspecified semantic representations are inferred from the syntactic structure, leaving space for subsequent addition of reinterpretation operators. Unfortunately, a structural danger of overgeneration is inherent to the relaxation of underspecified semantic representations. We identify the problem and distinguish structural properties that avoid it. We furthermore develop techniques for proving these properties and apply them to prove the safety of relaxation in a prototypical syntax/semantics interface. In doing so, we present some novel properties of tree descriptions in the constraint language over lambda structures (CLLS).},
  year =  {2000}
}


@InProceedings{DucTha99,
  author =       {Denys Duchier and Stefan Thater},
  title =        {Parsing with Tree Descriptions: a constraint-based approach},
  booktitle =    {Sixth International Workshop on Natural
Language Understanding and Logic Programming},
  year =         1999,
  pages =       {17--32},
  abstract = {We describe a grammatical formalism based on tree descriptions and
develop a constraint-based treatment of parsing in that framework. We
introduce the language of electrostatic tree descriptions to write
lexical entries: these are tree descriptions using neutral, as well as
positively and negatively charged variables. We develop an appropriate
notion of model. We then extend the framework to disjunctive systems
of electrostatic descriptions, and we correspondingly extend the
notion of model. Then we show how the search for minimal models can be
realized by reduction to a CSP solvable by constraint programming and
we provide the full encoding in an axiomatic style.},
  ma-key={duchier@ps.uni-sb.de stth@coli.uni-sb.de},
  project-key={C1 C2 C3}
}




@InProceedings{WilMan99,
  author = 	 {A.~Willis and S.~Manandhar},
  title = 	 {Two Accounts of Scope Availability and Semantic Underspecification},
  booktitle = 	 proc#{37th annual meeting of the }#ACL,
pages     = {293--300},
  year =	 1999
}

@InProceedings{KemMey99,
  author = 	 {Ruth Kempson and Wilfried Meyer-Viol},
  title = 	 {The dynamics of tree growth and quantifier construal},
  booktitle = 	 {Proceedings of the 12th Amsterdam Colloquium},
  year =	 1999
}



@InProceedings{Per00,
  author = 	 {Guy Perrier},
  title = 	 {From Intuitionistic Proof Nets to Interaction Grammars},
  booktitle = 	 {Proceedings of the 5th TAG+ Workshop},
  year =	 2000,
  address =	 {Paris}
}

@InProceedings{RamVSWei95,
  author = 	 {O. Rambow and K. Vijay-Shanker and D. Weir},
  title = 	 {{D-Tree} Grammars},
  booktitle = 	 proc#{33rd annual meeting of the }#ACL,
  pages =	 {151--158},
  year =	 1995
}

@Misc{LEDA,
  author = {LEDA},
  year = 2000,
  title =	 {The {LEDA} {L}ibrary},
  howpublished = {Web page at \url{http://www.mpi-sb.mpg.de/LEDA/}}
}

@Book{MehNae99,
  author =	 {K.~Mehlhorn and S.~N{\"a}her},
  title = 	 {The {LEDA} Platform of Combinatorial and Geometric Computing},
  publisher = 	 {Cambridge University Press},
  year = 	 1999,
  address =	 {Cambridge},
  note = {See also \url{http://www.mpi-sb.mpg.de/LEDA/}}
}

@Article{GalMicGab86,
  author = 	 {Z. Galil and S. Micali and H. N. Gabow},
  title = 	 {An {$O(EV \log V)$} algorithm for finding a maximal weighted matching in general graphs},
  journal = 	 {SIAM Journal of Computing},
  year = 	 1986,
  volume =	 15,
  pages =	 {120--130}
}

@Article{AhoGarUll72,
  author        = {A. V. Aho and M. R. Garey and J. D. Ullman},
  title         = {The transitive reduction of a directed graph},
  journal       = {SIAM Journal of Computing},
  volume        = {1},
  year          = {1972},
  pages         = {131--137},
  abstract      = {We consider economical representations for the path
                  information in a directed graph. A directed graph $G^t$ is
                  said to be a transitive reduction of the directed graph $G$
                  provided that (i) $G^t$ has a directed path from vertex $u$
                  to vertex $v$ if and only if $G$ has a directed path from
                  vertex $u$ to vertex $v$, and (ii) there is no graph with
                  fewer arcs than $G^t$ satisfying condition (i). Though
                  directed graphs with cycles may have more than one such
                  representation, we select a natural canonical
                  representative as the transitive reduction for such graphs.
                  It is shown that the time complexity of the best algorithm
                  for finding the transitive reduction of a graph is the same
                  as the time to compute the transitive closure of a graph or
                  to perform Boolean matrix multiplication.},
  keywords      = {Directed graph, binary relation, minimal representation,
                  transitive reduction, algorithm, transitive closure, matrix
                  multiplication, computational complexity}
}


@article{ThatcherWright:67,
   author = {Thatcher, J. W. and Wright, J. B.},
   journal = {Mathematical Systems Theory},
   month = {August},
    number = {1},
   pages = {57--81},
   title = {Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic},
   volume = {2},
   year = {1967}
}
@InProceedings{Cornell94,
  author = 	 {Thomas Cornell},
  title = 	 {On Determining the Consistency of Partial
  Descriptions of Trees},
  booktitle = 	 proc #{32th Annual Meeting of the }#ACL,
  pages = 	 {163-170},
  year = 	 1994
}
@InProceedings{VSWeiRam95,
  author = 	 {K. Vijay-Shanker and David Weir and Owen Rambow},
  title = 	 {{Parsing D-Tree Grammars}},
  booktitle = 	 {Proceedings of the International Workshop on Parsing Technologies},
  year =	 1995
}


@string{LNCS = {Lecture Notes in Computer Science}}
@string{springer= {Springer-Verlag}}

@InProceedings{DucNie00,
  author =       {Denys Duchier and Joachim Niehren},
  title =        {Dominance Constraints with Set Operators},
  booktitle =    proc#{First International Conference on Computational Logic},
  key  = {d1},
  year =        2000,
  pages = {326-341},
  number = {1861},
  series =       LNCS,
  publisher =    springer,
  abstract = {Dominance constraints are widely used in computational 
linguistics as a language for talking and 
reasoning about trees. In this paper, we extend dominance
constraints by admitting 
set operators. Set operators contribute 
a controlled form of disjunction that is emminently well-suited for 
constraint propagation. We present a solver for dominance
constraints with set operators as a system of abstract
propagation and distribution rules, and prove its soundness 
and completeness. We then
derive an efficient implementation in a constraint programming 
language with finite sets and prove its 
faithfullness to the abstract inference rules.},
  project-key={C1 C3 C4},
  ma-key={duchier@ps.uni-sb.de niehren@ps.uni-sb.de niehren@coli.uni-sb.de}
}



@InProceedings{SODA2001,
  author = 	 {E.~Althaus and D.~Duchier and A.~Koller 
                and K.~Mehlhorn and J.~Niehren and S.~Thiel},
  title = 	 {An Efficient Algorithm for the Configuration Problem of  Dominance Graphs},
  booktitle = 	 {Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms},
  year =	 2001,
  pages =        {815--824},
}

@InProceedings{KolMehNie00,
  author = {Alexander Koller and Kurt Mehlhorn and Joachim Niehren},
  title  = {A Polynomial-Time Fragment of Dominance Constraints},
  booktitle =  {Proceedings of the 38th Annual Meeting of the
                Association of Computational Linguistics},
  year      = 2000,
  pages     = {368--375},
  project-key={C4},
  ma-key={niehren@ps.uni-sb.de koller@coli.uni-sb.de},
  abstract={Dominance constraints are a logical language
for describing trees that is widely used in
computational linguistics. Their general satisfiability
problem is known to be NP-complete. Here we identify
\emph{normal} dominance constraints, a natural
fragment whose satisfiability problem we show to be in polynomial
time. We present a quadratic satisfiability algorithm and use it in
another algorithm that enumerates solutions efficiently. Our result is
useful for various applications of dominance constraints and related
formalisms.}
}


@Article{clls2000,
  key = {a2},
  author =       {M.~Egg and A.~Koller and J.~Niehren},
  title =        {The Constraint Language for Lambda Structures},
  journal =      {Journal of Logic, Language, and Information},
  year =         {2001},
  volume = {10},
  pages = {457-485},
  abstract={This paper presents the Constraint Language for Lambda Structures
(CLLS), a first-order language for semantic underspecification that
conservatively extends dominance constraints. It is interpreted over
lambda structures, tree-like structures that encode lambda-terms. Based on
CLLS, we present an underspecified, uniform analysis of scope,
ellipsis, anaphora, and their interactions. CLLS solves a variable
capturing problem that is omnipresent in scope underspecification and
can be processed efficiently.},
  project-key={C1 C4},
  ma-key={egg@coli.uni-sb.de koller@coli.uni-sb.de niehren@ps.uni-sb.de
        niehren@coli.uni-sb.de}
}

@Article{processing00,
  key = {a1},
  author =       {K.~Erk and A.~Koller and J.~Niehren},
  title =        {Processing Underspecified Semantic Representations in 
        the Constraint Language for Lambda Structures},
  journal =      {Research on Language and
                   Computation},
  year =         {2003},
  publisher = Kluwer,
  volume = {1},
pages={127--169},
abstract={The constraint language for lambda structures (CLLS)
is an expressive language of tree descriptions which combines
dominance constraints with powerful parallelism and binding
constraints. CLLS was introduced as a uniform framework for defining
underspecified semantics representations of natural language
sentences, covering scope, ellipsis, and anaphora. This article
presents saturation-based algorithms for processing the complete
language of CLLS. It also gives an overview of previous results on 
questions of processing and complexity.},
        project-key={C4},
        ma-key={erk@ps.uni-sb.de koller@coli.uni-sb.de
        niehren@ps.uni-sb.de niehren@coli.uni-sb.de}
}

@Article{RecordsLogProg,
author  = "Gert Smolka and Ralf Treinen",
title   = "Records for Logic Programming",
journal = "Journal of Logic Programming",
volume  = 18,
number  = 3,
year    = 1994,
month   = apr,
pages   = "229--258",
directory = "ProgrammingSysLab",
filename = "RecordsLogProg.ps.gz, Records.LogProg.dvi.gz",
}





@PhdThesis{BosThesis02,
  author = 	 {J.~Bos},
  title = 	 {Underspecification and resolution in discourse semantics},
  school = 	 {Saarland University},
  year = 	 2002
}

@InProceedings{Hobbs83,
  author = 	 {Jerry Hobbs},
  title = 	 {An Improper Treatment of Quantification in Ordinary English},
  booktitle = 	 proc#{21st annual meeting of the }#ACL,
  pages =	 {57--63},
  year =	 1983,
}


@Article{Egg98:MRS,
  author = 	 {Markus Egg},
  title = 	 {\textit{Wh}-questions in Underspecified Minimal Recursion Semantics},
  journal = 	 {Journal of Semantics},
  year = 	 1998,
  volume =	 15,
  pages =	 {37--82}
}

@Article{Althaus-J.Algo.,
  author = 	 {E.~Althaus and D.~Duchier and A.~Koller 
             and K.~Mehlhorn and J.~Niehren and S.~Thiel},
  title = 	 {An Efficient Graph Algorithm for Dominance 
             Constraints},
  journal = 	 {Journal of Algorithms},
  year = 	 2003,
  volume = {48},
  number = {1},
  pages = {194--219}
}

@Misc{thiel02,
  author =	 {Sven Thiel},
  title =	 {A linear time algorithm for the configuration problem of dominance graphs},
  howpublished = {Submitted},
  year =	 2002
}




@PhdThesis{thiel-thesis03,
  author = 	 {Sven Thiel},
  title = 	 {Efficient Algorithms for Constraint Propagation and for Processing Tree Descriptions},
  school = 	 {Department of Computer Science, Saarland University},
  year = 	 2004
}

@InProceedings{BodErkKolNie01b, 
   author = {Manuel Bodirsky and Katrin Erk and Alexander Koller and 
             Joachim Niehren}, 
   title  = {Underspecified Beta Reduction}, 
   year   = 2001, 
   booktitle = {Proceedings of the 39th ACL}, 
   address = {Toulouse} 
} 

@InProceedings{BodErkKolNie01a, 
   author = {Manuel Bodirsky and Katrin Erk and Alexander Koller and 
             Joachim Niehren}, 
   title  = {Beta Reduction Constraints}, 
   year   = 2001, 
   booktitle = {Proceedings of the 12th International Conference on 
             Rewriting Techniques and Applications}, 
   address = {Utrecht} 
} 

@InProceedings{ErkKol01, 
   author = {Katrin Erk and Alexander Koller}, 
   title  = {{VP} Ellipsis by Tree Surgery}, 
   year   = 2001, 
   booktitle = {Proceedings of the 13th Amsterdam Colloquium}, 
   address = {Amsterdam} 
} 

@Misc{KolNie00a, 
   author = {Alexander Koller and Joachim Niehren}, 
   title  = {Constraint Programming in Computational Linguistics}, 
   year   = 2000, 
   howpublished = {To appear in Proceedings of LLC8, CSLI Press} 
} 

@InProceedings{KolNieTha03, 
   author = {Alexander Koller and Joachim Niehren and Stefan 
             Thater}, 
   title  = {Bridging the Gap Between Underspecification Formalisms: 
             Hole Semantics as Dominance Constraints}, 
   year   = 2003, 
   booktitle = {Proceedings of the 11th EACL}, 
   address = {Budapest} 
} 


@InProceedings{KolNie00b, 
   author = {Alexander Koller and Joachim Niehren}, 
   title  = {On Underspecified Processing of Dynamic Semantics}, 
   year   = 2000, 
   booktitle = {Proceedings of COLING-2000}, 
   address = {Saarbr{\"u}cken} 
} 


@InProceedings{JasKol99, 
   author = {Jan Jaspars and Alexander Koller}, 
   title  = {A Calculus for Direct Deduction with Dominance 
             Constraints}, 
   year   = 1999, 
   booktitle = {Proceedings of the Twelfth Amsterdam Colloquium}, 
   address = {Amsterdam} 
} 

@InProceedings{KolStr02, 
   author = {Alexander Koller and Kristina Striegnitz}, 
   title  = {Generation as Dependency Parsing}, 
   year   = 2002, 
   booktitle = {Proceedings of the 40th ACL}, 
   address = {Philadelphia} 
} 

@InProceedings{KolNieStr99, 
   author = {Alexander Koller and Joachim Niehren and Kristina 
             Striegnitz}, 
   title  = {Relaxing Underspecified Semantic Representations for 
             Reinterpretation}, 
   year   = 1999, 
   booktitle = {Proceedings of the Sixth Meeting on Mathematics of 
             Language (MOL6)}, 
   address = {Orlando, Florida} 
} 

@INPROCEEDINGS{rade-acl2001,
  title = {Topological Dependency Trees: A Constraint-based Account of Linear Precedence},
  year = {2001},
  author = {Denys Duchier and Ralph Debusmann},
  abstract = {Linear precedence in so-called free word order languages remains challenging for modern grammar formalisms.  To address this issue,
 we describe a new framework for dependency grammar, with a modular
 decomposition of immediate dependency and linear precedence.  Our
 approach distinguishes two orthogonal yet mutually constraining
 structures: a syntactic dependency tree (ID tree) and a topological
 dependency tree (LP tree).  The ID tree is non-projective, and even
 non-ordered, and
 its edges are labeled by syntactic roles. The LP tree is
 projective, partially ordered, and its edges are labeled by
 topological fields.  The shape of the LP tree is a
 flattening of the ID tree's obtained by allowing nodes to `climb
 up'.  Our theory of ID/LP trees is formulated in terms of
 (a) lexicalized constraints and (b) principles governing e.g. climbing
 conditions.  We illustrate it with a detailed account of word order
 phenomena in the verbal complex of German verb final sentences.},
  booktitle = {Proceedings of the 39th ACL},
  address = {Toulouse, France},
  ma-key = {duchier@ps.uni-sb.de},
  sline = 980,
  project-key = {C1 C3},
  label = {rade-acl2001}
}





@Article{duchier-jlac2000,
  author = 	 {Denys Duchier},
  title = 	 {Configuration Of Labeled Trees Under Lexicalized Constraints And Principles},
  journal = 	 {Research on Language and Computation},
  year = 	 2003,
 abstract = {Trees with labeled edges have widespread applicability, for example for the representation of dependency syntax trees.  Given a fixed
 number of nodes and constraints on how edges may be drawn between
 them, to find solution trees is known as a `configuration' problem.
 In this paper, we formalize the configuration problem of labeled trees
 and argue that it can be regarded as a constraint satisfaction problem
 which can be solved directly and efficiently by constraint
 propagation. Our approach takes advantage of constraints on finite
 sets as well as of a new family of `selection' constraints.  We
 further entertain various reinements of interest to the computational
 linguist such as lexical ambiguity, valency constraints, and
 grammatical principles.
 
 This framework generalizes our MOL6 presentation
 \textit{``Axiomatizing Dependency Parsing Using Set Constraints''}
 which addressed the treatment of immediate syntactic dependence when
 parsing with a dependency grammar and paves the way for a
 corresponding treatment of linear precedence based on a notion of
 topological rather than syntactic dependencies.},
  note =	 {To appear}
}


@Article{KolDebGabStr03,
  author = 	 {Alexander Koller and Ralph Debusmann and Malte Gabsdil 
             and Kristina Striegnitz},
  title = 	 {Put my galakmid coin into the dispenser and kick it: 
             Computational Linguistics and Theorem Proving in a 
             Computer Game},
  journal = 	 {Journal of Logic, Language, and Information},
  year = 	 2004,
  volume = 13,
  number = 2,
  pages = {187--206}
}

@INPROCEEDINGS{wellnested,
  title = {Well-Nested  Parallelism  Constraints  for  Ellipsis  Resolution},
  year = {2003},
  author = {Katrin Erk and Joachim Niehren},
  booktitle = {11th  Conference  of  the  European    Chapter  of  the  Association  of  Computational  Linguistics},
  pages = {115--122},
}

@InCollection{weidenbach99:_spass,
  author = 	 {Christoph Weidenbach},
  title = 	 {{SPASS}: {C}ombining superposition, sorts, and splitting},
  booktitle = 	 {Handbook of Automated Reasoning},
  publisher =	 {Elsevier},
  year =	 1999,
  editor =	 {A.~Robinson and V.~Voronkov}
}


 @Article{milsark77:_towar_englis,
  author = 	 {Gary Milsark},
  title = 	 {Towards an explanation of certain peculiarities in the existential construction in {E}nglish},
  journal = 	 {Linguistic Analysis},
  year = 	 1977,
  volume =	 3,
  pages =	 {1--30}
}

@InCollection{geurts03:_exist,
  author = 	 {Bart Geurts},
  title = 	 {Existential import},
  booktitle = 	 {Existence: Syntax and Semantics},
  publisher =	 {Kluwer},
  year =	 2003,
  editor =	 {E.~Comorovski and K.~von Heusinger},
  note =	 {To appear}
}



@Article{geurts03:_reason,
  author = 	 {Bart Geurts},
  title = 	 {Reasoning with quantifiers},
  journal = 	 {Cognition},
  year = 	 2003,
  volume =	 86,
  pages =	 {223--251}
}

@Article{lappin88:_presup,
  author = 	 {Shalom Lappin and Tanya Reinhart},
  title = 	 {Presuppositional effects of strong determiners: a processing account},
  journal = 	 {Linguistics},
  year = 	 1988,
  volume =	 26,
  pages =	 {1021--1037}
}

@Article{lasersohn93:_exist_presup_backg_knowl,
  author = 	 {Peter Lasersohn},
  title = 	 {Existence Presuppositions and Background Knowledge},
  journal = 	 {Journal of Semantics},
  year = 	 1993,
  volume =	 10,
  pages =	 {113--122}
}

@InCollection{jong85:_gener,
  author = 	 {Franciska de Jong and Henk Verkuyl},
  title = 	 {Generalized quantifiers: The properness of their strength},
  booktitle = 	 {Generalized Quantifiers in Natural Language},
  pages =	 {21--43},
  publisher =	 {Foris Publications},
  year =	 1984,
  editor =	 {J.~van Benthem and A.~ter Meulen},
  address =	 {Dordrecht}
}



@Article{strawson64:_ident,
  author = 	 {P. F. Strawson},
  title = 	 {Identifying reference and truth-values},
  journal = 	 {Theoria},
  year = 	 1964,
  volume =	 30,
  pages =	 {96--118},
  note =	 {Reprinted in: \textit{Logico-Linguistic Papers}, 75--95. Methuen, London, 1974. \todo{noch nicht gefunden}}
}


@Article{sandt99:_presup,
  author = 	 {Rob van der Sandt},
  title = 	 {Presupposition projection as anaphora resolution},
  journal = 	 {Journal of Semantics},
  year = 	 1999,
  volume =	 9,
  pages =	 {333--377}
}

@Article{egg03:_begin,
  author = 	 {Markus Egg},
  title = 	 {Beginning novels and finishing hamburgers -- remarks on the semantics of \textit{to begin}},
  journal = 	 {Journal of Semantics},
  year = 	 2003,
  volume =	 20,
  pages =	 {163--191}
}

@INPROCEEDINGS{GK:transitive-reduction,
  AUTHOR       = {Goralcikova, A. and Koubek, V.}, 
  TITLE        = {A reduct-and-closure algorithm for graphs},
  BOOKTITLE    = {Proceedings of the 8th Symposium on Mathematical Foundations of Computer Science},
  PADDRESS     = {Berlin},
  PUBLISHER    = {Springer},
  YEAR         = {1979},
  SERIES       = {LNCS},
  VOLUME       = {74},
  PAGES        = {301--307},
}

@ARTICLE{Simon:transitive-closure,
AUTHOR        = {Simon, Klaus}, 
TITLE         = {An Improved Algorithm for Transitive Closure on Acyclic Digraphs},
YEAR          = {1988},
JOURNAL       = {Theoretical Computer Science},
VOLUME        = {58},
NUMBER        = {1--3},
PAGES         = {325--346},
LOCATION      = {MPI-ZB},
BIBTYPE       = {ARTICLE},
}

@ARTICLE{GKT:alternating-cycle-test,
AUTHOR        = {Gabow, H.N. and Kaplan, H. and Tarjan, R.E.}, 
TITLE         = {Unique Maximum Matching Algorithms},
YEAR          = {2001},
JOURNAL       = {Journal of Algorithms},
VOLUME        = {40},
PAGES         = {159--183},
LOCATION      = {MPI-ZB},
BIBTYPE       = {ARTICLE},
}

@InProceedings{bodirsky-weakly-normal-constraints,
author = {Manuel Bodirsky and Denys Duchier and
Joachim Niehren and Sebastian Miele}, 
title = {A New Algorithm for
Normal Dominance Constraints}, 
year = {2004}, 
booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)}
}

 @INPROCEEDINGS{mrs-dom,
   title  =  {Bridging  the  Gap  Between  Underspecification  Formalisms:  Minimal  Recursion  Semantics  as  Dominance  Constraints},
   year  =  {2003},
   author  =  {Joachim  Niehren  and  Stefan  Thater},
   abstract  =  {Minimal  Recursion  Semantics  (MRS)  is  the  standard  formalism  used  in  large-scale  HPSG  grammars  to  model  underspecified  semantics.  We
 present  the  first  provably  efficient  algorithm  to  enumerate  the
 readings  of  MRS  structures.  It  is  obtained  by  translating  MRS
 into  normal  dominance  constraints  for  which  efficient
 algorithms  exist.},
   booktitle  =  {{41st  Meeting  of  the  Association  of  Computational  Linguistics}},
   pages  =  {367--374},
   sline  =  {1s[0]=1ues[0]=1s[0]=1},
   label  =  {mrs_dom}
}


@InCollection{heim83:_file,
  author = 	 {Irene Heim},
  title = 	 {File change semantics and the familarity theory of definiteness},
  booktitle = 	 {Meaning, use, and interpretation of language},
  publisher =	 {De Gruyter},
  year =	 1983,
  editor =	 {R. Bauerle and C. Schwarze and A. von Stechow}
}

@INPROCEEDINGS{duchier-amilp-2000,
  title = {A Model-Eliminative Treatment of Quantifier-free Tree Descriptions},
  year = {2000},
  author = {Denys Duchier},
  abstract = {Tree descriptions are widely used in computational linguistics for talking and reasoning about trees.  For practical applications,
 it is essential to be able to decide satisfiability and enumerate
 solutions efficiently.  This challenge cannot realistically be met by
 brute force enumeration.  However it can be addressed very effectively
 by constraint propagation as provided by modern constraint technology.
 
 Previously, we studied the conjunctive fragment of tree descriptions
 and showed how the problem of finding minimal models of a conjunctive
 tree description could be transformed into a constraint satisfaction
 problem (CSP) on finite set variables.
 
 In this paper, we extend our account to the fragment that admits both
 negation and disjunction, but still leaves out quantification.  Again
 we provide a reduction to a CSP.  While our previous encoding
 introduced the reader to set constraints and disjunctive propagators,
 we now extend our arsenal with selection propagators.},
  booktitle = {Algebraic Methods in Language Processing, AMILP~2000, TWLT~16},
  pages = {55--66},
  editor = {D. Heylen and A. Nijholt and G. Scollo},
  series = {Twente Workshop on Language Technology (2nd AMAST Workshop on Language Processing)},
  address = {Iowa City, USA},
  publisher = {Universiteit Twente, Faculteit Informatica},
  ma-key = {duchier@ps.uni-sb.de},
  sline = 1698,
  project-key = {C3},
  label = {duchier-amilp}
}


@InProceedings{niehren03:_descr_lambd_terms_contex_unific,
  author = 	 {Joachim Niehren and Mateu Villaret},
  title = 	 {Describing Lambda-Terms in Context Unification},
  booktitle =	 {Proceedings of the Fourth International Workshop on Inference in Computational Semantics (ICOS-4)},
  year =	 2003,
  editor =	 {Patrick Blackburn and Johan Bos},
  address =	 {Nancy}
}

@InProceedings{dienes03:_statis,
  author = 	 {P{\'e}ter Dienes and Alexander Koller and Marco Kuhlmann},
  title = 	 {Statistical {A$^*$} dependency parsing},
  booktitle =	 {Proceedings of the Lorraine-Saarland Workshop on Prospects and Advances in the Syntax-Semantics Interface},
  year =	 2003,
  editor =	 {Denys Duchier and Geert-Jan Kruijff},
  address =	 {Nancy}
}

@INPROCEEDINGS{duchier-mol6,
  title = {Axiomatizing Dependency Parsing Using Set Constraints},
  year = {1999},
  author = {Denys Duchier},
  abstract = {We propose a new formulation of dependency grammar and develop a corresponding axiomatization of syntactic well-formedness with a
 natural reading as a concurrent constraint program. We demonstrate the
 expressivity and effectiveness of set constraints, and describe a
 treatment of ambiguity with wide applicability. Further, we provide a
 constraint programming account of dependent disjunctions that is both
 simple and efficient and additionally provides the benefits of
 constructive disjunctions. Our approach was implemented in Oz and
 yields parsers with very good performance for our currently middle
 scale grammars. Constraint propagation can be observed to be
 remarkably effective in pruning the search space.},
  booktitle = {Sixth Meeting on Mathematics of Language},
  address = {Orlando, Florida},
  pages = {115--126},
  ma-key = {duchier@ps.uni-sb.de},
  sline = 2564,
  project-key = {C1 C3},
  label = {duchier-mol6}
}

@InCollection{joshi;etal1997,
  author = 	 {Aravind Joshi and Yves Schabes},
  title = 	 {Tree-{A}djoining {G}rammars},
  booktitle = 	 {Handbook of Formal Languages},
  pages =	 {69--123},
  publisher =	 {Springer-Verlag},
  year =	 1997,
  editor =	 {G. Rozenberg and A. Salomaa},
  chapter =	 2,
  address =	 {Berlin}
}

@InProceedings{Kay96,
  author = 	 {Martin Kay},
  title = 	 {Chart Generation},
  booktitle = 	 {Proceedings of the 34th Annual Meeting of the ACL},
  pages =	 {200-204},
  year =	 1996,
  address =	 {Santa Cruz}
}

@InProceedings{shieber88,
  author = 	 {Stuart Shieber},
  title = 	 {A Uniform Architecture for Parsing and Generation},
  booktitle = 	 {Proceedings of COLING-88},
  year =	 1988,
  address =	 {Budapest}
}

@InProceedings{StoneDoran97,
  author = 	 {Matthew Stone and Christy Doran},
  title = 	 {Sentence Planning as Description Using Tree-Adjoining Grammar},
  booktitle = 	 {Proceedings of the 35th ACL},
  pages =	 {198--205},
  year =	 1997
}


@Book{BarBerRis87,
  author =	 {G. Edward Barton and Robert C. Berwick and Eric Sven Ristad},
  title = 	 {Computational Complexity and Natural Language},
  publisher = 	 {MIT Press},
  year = 	 1987,
  address =	 {Cambridge, Mass.}
}

@MastersThesis{Suhre99,
  author = 	 {Oliver Suhre},
  title = 	 {Computational Aspects of a Grammar Formalism for Languages with Freer Word Order},
  school = 	 {Department of Informatics, Eberhard-Karls-Universit{\"a}t T{\"u}bingen},
  year = 	 1999
}

@TechReport{xtag01:_tr,
  author =       {{XTAG Research Group}},
  title =        {A Lexicalized Tree Adjoining Grammar for English},
  institution =  {IRCS, University of Pennsylvania},
  year =         2001,
  number =       {IRCS-01-03}
}

@InProceedings{GarTha01,
  author = 	 {Claire Gardent and Stefan Thater},
  title = 	 {Generating with a grammar based on tree descriptions: {A} constraint-based approach},
  booktitle = 	 {Proceedings of the 39th ACL},
  year =	 2001,
  address =	 {Toulouse}
}

@InProceedings{carroll99,
  author = 	 {John Carroll and Ann Copestake and Dan Flickinger and Victor Poznanski},
  title = 	 {An efficient chart generator for (semi-)lexicalist grammars},
  booktitle = 	 {Proceedings of the 7th European Workshop on NLG},
  pages =	 {86--95},
  year =	 1999,
  address =	 {Toulouse}
}

@Article{schabes94,
  author = 	 {Yves Schabes and Stuart Shieber},
  title = 	 {An alternative conception of tree-adjoining derivation},
  journal = 	 {Computational Linguistics},
  year = 	 1994,
  volume =	 20,
  number =	 1,
  pages =	 {91--124}
}

@InProceedings{Brew92,
  author = 	 {Chris Brew},
  title = 	 {Letting the cat out of the bag: {G}eneration for {S}hake-and-{B}ake {MT}},
  booktitle = 	 {Proceedings of COLING-92},
  pages =	 {610--616},
  year =	 1992,
  address =	 {Nantes}
}


@InProceedings{moore02:_compl_effic_senten_realiz_algor_unific_gramm,
  author = 	 {Robert C. Moore},
  title = 	 {A Complete, Efficient Sentence-Realization Algorithm for Unification Grammar},
  booktitle =	 {Proceedings of the International Natural Language Generation Conference (INLG'02)},
  pages =	 {41--48},
  year =	 2002,
  address =	 {New York}
}


@InProceedings{resnik92:_probab,
  author =       {Philip Resnik},
  title =        {Probabilistic tree-adjoining grammars as a framework for statistical natural language processing},
  booktitle =    {Proceedings of the 15th COLING},
  pages =        {418--424},
  year =         1992,
  address =      {Nantes}
}


@InProceedings{chen00:_autom_tags_penn_treeb,
  author = 	 {John Chen and K. Vijay-Shanker},
  title = 	 {Automated extraction of {TAG}s from the {P}enn {T}reebank},
  booktitle =	 {Proceedings of the 6th International Workshop on Parsing Technologies},
  year =	 2000,
  address =	 {Trento, Italy}
}


@InProceedings{bangalore00:_exploit_probab_hierar_model_gener,
  author = 	 {Srinivas Bangalore and Owen Rambow},
  title = 	 {Exploiting a Probabilistic Hierarchical Model for Generation},
  booktitle =	 {Proceedings of the 18th COLING},
  year =	 2000,
  address =	 {Saarbr{\"u}cken}
}


@InProceedings{Debusmann-passi03,
  author = {Ralph Debusmann},
  authorURLs = {http://www.ps.uni-sb.de/~rade/},
  title = {Dependency Grammar as Graph Description},
  year = 2003,
  booktitle = {Prospects and Advances in the Syntax/Semantics Interface},
  editor = {Denys Duchier},
  publisher = {LORIA},
  address = {Nancy/FRA},
  series = {Lorraine-Saarland Workshop Series},
  pages = {79--84},
  abstract = {The paper introduces a generalisation of the grammar
  formalism of Topological Dependency Grammar (TDG) (Duchier and
  Debusmann 2001).  The result, eXtensible Dependency Grammar (XDG),
  is a description language for sets of labeled directed
  graphs. Lexicalisation turns XDG into a powerful dependency-based
  meta grammar formalism.  As an instance of XTDG, we present Semantic
  Topological Dependency Grammar (STDG), a new dependency-based
  grammar formalism with a syntax-semantics interface to
  underspecified semantics.},
  keywords = {dependency-grammar, meta-grammar},
  note = {}
}


@InProceedings{dincbas88:_chip,
  author = 	 {Mehmet Dincbas and Pascal van Hentenrynck and Helmut Simonis and Abderrahmane Aggoun and Thomas Graf and F. Berthier},
  title = 	 {The constraint logic programming language CHIP},
  booktitle =	 {Proceedings of the International Conference on Fifth Generation Computer Systems FGCS-88},
  pages =	 {693--702},
  year =	 1988,
  address =	 {Tokyo}
}

@InProceedings{gervet94:_conjun,
  author = 	 {Carmen Gervet},
  title = 	 {Conjunto: Constraint Logic Programming with Finite Set Domains},
  booktitle =	 {Proceedings of the International Logic Programming Symposium (ILPS '94)},
  pages =	 {339--358},
  year =	 1994
}

@InCollection{maxwell91,
  author = 	 {John T. Maxwell and Ronald M. Kaplan},
  title = 	 {A method for disjunctive constraint satisfaction},
  booktitle = 	 {Current Issues in Parsing Technology},
  pages =	 {173--190},
  publisher =	 {Kluwer Academic Publishers},
  year =	 1991,
  editor =	 {Masaru Tomita}
}


@Article{younger67:_recog,
  author = 	 {D. Younger},
  title = 	 {Recognition and parsing of context-free languages in time $n^3$},
  journal = 	 {Information and Control},
  year = 	 1967,
  volume =	 10,
  number =	 2,
  pages =	 {189--208}
}

@Article{earley70,
  author = 	 {J. Earley},
  title = 	 {An efficient context-free parsing algorithm},
  journal = 	 {Communications of the ACM},
  year = 	 1970,
  volume =	 13,
  number =	 2,
  pages =	 {94--102}
}

@InCollection{kay86:_algor,
  author = 	 {Martin Kay},
  title = 	 {Algorithm schemata and data structures in syntactic processing},
  booktitle = 	 {Readings in Natural Language Processing},
  pages =	 {35--70},
  publisher =	 {Morgan Kaufmann},
  year =	 1986,
  editor =	 {Barbara J. Grosz and Karen Sparck-Jones and Bonnie Lynn Webber},
  address =	 {Los Altos},
  annote = {Accessible reference for chart parsing}
}

@Article{hays64:_depen,
  author = 	 {David Hays},
  title = 	 {Dependency theory: {A} formalism and some observations},
  journal = 	 {Language},
  year = 	 1964,
  volume =	 40,
  pages =	 {511--525}
}

@InProceedings{dowding94:_inter_syntax_seman_effic_bottom_up_parser,
  author = 	 {John Dowding and Robert Moore and Francois Andry and Douglas B. Moran},
  title = 	 {Interleaving Syntax and Semantics in an Efficient Bottom-Up Parser},
  booktitle =	 {Proceedings of the 32nd ACL},
  pages =	 {110--116},
  year =	 1994,
  address =	 {Las Cruces}
}

@InProceedings{schuler02:_inter,
  author = 	 {William Schuler},
  title = 	 {Interleaved semantic interpretation in environment-based parsing},
  booktitle =	 {Proceedings of the 19th COLING},
  year =	 2002,
  address =	 {Taipei}
}

@Article{gabsdil00:_class_scope_ambig,
  author = 	 {Malte Gabsdil and Kristina Striegnitz},
  title = 	 {Classifying Scope Ambiguities},
  journal = 	 {Journal of Language and Computation},
  year = 	 2000,
  volume =	 1,
  number =	 2,
  pages =	 {307--313}
}


@Article{reiter97:_build,
  author = 	 {Ehud Reiter and Robert Dale},
  title = 	 {Building applied natural language generation systems},
  journal = 	 {Journal of Natural Language Engineering},
  year = 	 1997,
  volume =	 3,
  pages =	 {57--87}
}

@Book{apt03:_princ_const_progr,
  author =	 {Krzysztof R. Apt},
  title = 	 {Principles of Constraint Programming},
  publisher = 	 {Cambridge University Press},
  year = 	 2003
}




@InCollection{bever70,
  author = 	 {Thomas G. Bever},
  title = 	 {The cognitive basis for linguistic structures},
  booktitle = 	 {Cognition and the Development of Language},
  publisher =	 {Wiley},
  year =	 1970,
  editor =	 {John R. Hayes},
  address =	 {New York}
}



@InProceedings{FucKolNieTha04,
  author = 	 {Ruth Fuchss and Alexander Koller and Joachim Niehren 
             and Stefan Thater },
  title = 	 {Minimal Recursion Semantics as Dominance Constraints: 
             Translation, Evaluation, and Analysis},
  booktitle =	 {Proceedings of the 42nd ACL},
  year =	 2004,
  address =	 {Barcelona}
}


@Book{Copestake:LKB-Book,
  author =       {Copestake, Ann},
  title =        {Implementing Typed Feature Structure Grammars},
  publisher =    {CSLI Publications},
  year =         2002,
  address =      {Stanford, CA}
}


@InProceedings{Copestake&Flickinger:LKB,
  author =	 {Copestake, Ann and Flickinger, Dan},
  title =	 {An open-source grammar development environment and broad-coverage English grammar using {HPSG}},
  booktitle =	 {Conference on Language Resources and Evaluation},
  year =	 2000,
}

@InProceedings{Oepen&al:Redwoods,
  author =	 {Oepen, Stephan and Toutanova, Kristina and Shieber, Stuart and Manning, Christopher and Flickinger, Dan and Brants, Thorsten},
  title =	 {The {LinGO} {Redwoods} Treebank: Motivation and Preliminary Applications},
  booktitle =	 {Proceedings of the 19th International Conference on Computational Linguistics (COLING'02)},
  pages =	 {1253--1257},
  year =	 2002
}

@InProceedings{ebert03:_expres_compl_under_repres,
  author = 	 {Christian Ebert},
  title = 	 {On the Expressive Completeness of Underspecified Representations},
  booktitle =	 {Proceedings of the 14th Amsterdam Colloquium},
  year =	 2003,
  address =	 {Amsterdam}
}

@Article{bergmann81:_presup,
  author = 	 {Merrie Bergmann},
  title = 	 {Presupposition and two-dimensional logic},
  journal = 	 {Journal of Philosophical Logic},
  year = 	 1981,
  volume =	 10,
  pages =	 {27--54}
}


@InProceedings{kerber01:_reason_believ,
  author = 	 {Manfred Kerber and Michael Kohlhase},
  title = 	 {Reasoning without Believing: {O}n the Mechanization of Presuppositions and Partiality},
  booktitle =	 {Proceedings of the Third Intl. Workshop on Inference in Computational Semantics},
  year =	 2001,
  address =	 {Siena}
}

@InProceedings{chaves03:_non_redun_scope_disam_under_seman,
  author = 	 {Rui Pedro Chaves},
  title = 	 {Non-Redundant Scope Disambiguation in Underspecified Semantics},
  booktitle =	 {Proceedings of the Eighth ESSLLI Student Session},
  pages =	 {47--58},
  year =	 2003,
  editor =	 {Balder ten Cate},
  address =	 {Vienna}
}

@InProceedings{bodirsky02:_pure,
  author = 	 {Manuel Bodirsky and Martin Kutz},
  title = 	 {Pure dominance constraints},
  booktitle =	 {Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02)},
  pages =	 {287--298},
  year =	 2002,
  address =	 {Antibes -- Juan le Pins}
}

@InProceedings{AltKarKol04, 
   author = {Ernst Althaus and Nikiforos Karamanis and Alexander 
             Koller}, 
   title  = {Computing Locally Coherent Discourses}, 
   year   = 2004, 
   booktitle = {Proceedings of the 42nd ACL}, 
   address = {Barcelona} 
} 

 @INPROCEEDINGS{debusmann2004tag,
   title  =  {TAG  Parsing  as  Model  Enumeration},
   year  =  {2004},
   author  =  {Ralph  Debusmann  and  Denys  Duchier  and  Marco  Kuhlmann  and  Stefan  Thater},
   abstract  =  {This  paper  introduces  well-ordered  derivation  trees  and  makes  use  of  this  concept  in  a  novel  axiomatization  of  the  TAG  parsing  problem  as  a  constraint  satisfaction  problem.    Contrary  to  prior  approaches,  our  axiomatization  focuses  on  the  derivation  trees  rather  than  the  derived  trees.    Well-ordered  derivation  trees  are  our  primary  models,  whereas  the  derived  trees  serve  solely  to  determine  word  order.},
   booktitle  =  {{Seventh  International  Workshop  on  Tree  Adjoining  Grammar  and  Related  Formalisms  (TAG+7)}},
   address  =  {Vancouver,  Canada},
}

@InProceedings{DebDucKolKuhSmoTha04, 
   author = {Ralph Debusmann and Denys Duchier and Alexander Koller 
             and Marco Kuhlmann and Gert Smolka and Stefan Thater}, 
   title  = {A Relational Syntax-Semantics Interface Based on 
             Dependency Grammar}, 
   year   = 2004, 
   booktitle = {Proceedings of the 20th COLING}, 
   address = {Geneva} 
} 

@InProceedings{skut98:_german,
  author = 	 {Wojciech Skut and Thorsten Brants and Brigitte Krenn and Hans Uszkoreit},
  title = 	 {A linguistically interpreted corpus of {G}erman newspaper text},
  booktitle =	 {Proceedings of LREC-98},
  pages =	 {705--711},
  year =	 1998,
  address =	 {Granada},
annote = {negra}
}


@InProceedings{brants02:_tiger_treeb,
  author = 	 {Sabine Brants and Stefanie Dipper and Silvia Hansen and Wolfgang Lezius and George Smith },
  title = 	 {The {TIGER} {T}reebank},
  booktitle =	 {Proceedings of the Workshop on Treebanks and Linguistic Theories},
  year =	 2002,
  address =	 {Sozopol}
}

@InCollection{comon92:_compl,
  author = 	 {Hubert Comon},
  title = 	 {Completion of rewrite systems with membership constraints},
  booktitle = 	 {Coll. on Automata, Languages, and Programming},
  publisher =	 {Springer},
  year =	 1992,
  volume =	 623,
  series =	 {LNCS}
}

@Article{kallmeyer03:_factor_predic_argum_scope_seman,
  author = 	 {Laura Kallmeyer and Aravind K. Joshi},
  title = 	 {Factoring Predicate Argument and Scope Semantics: {U}nderspecified Semantics with {LTAG}},
  journal = 	 {Research on Language and Computation},
  year = 	 2003,
  volume =	 1,
  number =	 {1--2},
  pages =	 {3--58}
}


@InProceedings{steedman99:_alter_quant_scope_ccg,
  author = 	 {M. Steedman},
  title = 	 {Alternating Quantifier Scope in {CCG}},
  booktitle =	 {Proc. 37th ACL},
  pages =	 {301--308},
  year =	 1999
}




@InCollection{moortgat02:_categ,
  author = 	 {M. Moortgat},
  title = 	 {Categorial grammar and formal semantics},
  booktitle = 	 {Encyclopedia of Cognitive Science},
  publisher =	 {Nature Publishing Group, MacMillan},
  year =	 2002,
  note = {To appear}
}

@InProceedings{butt02:_paral_gramm_projec,
  author = 	 {Miriam Butt and Helge Dyvik and Tracy Holloway King and Hiroshi Masuichi and Christian Rohrer},
  title = 	 {The Parallel Grammar Project },
  booktitle =	 {Proceedings of COLING-2002 Workshop on Grammar Engineering and Evaluation},
  pages =	 {1--7},
  year =	 2002
}
 

@InCollection{keller88:_nested_cooper_storag,
  author = 	 {William R. Keller},
  title = 	 {Nested {C}ooper {S}torage: {T}he Proper Treatment of Quantification in Ordinary Noun Phrases},
  booktitle = 	 {Natural Language and Linguistic Theories},
  pages =	 {432--447},
  publisher =	 {Reidel},
  year =	 1988,
  editor =	 {U. Reyle and C. Rohrer},
  volume =	 35,
  series =	 {Studies in Linguistics and Philosophy}
}





@InCollection{poesio96:_seman,
  author = 	 {Massimo Poesio},
  title = 	 {Semantic ambiguity and perceived ambiguity},
  booktitle = 	 {\cite{DeemterPetersBook}},
  pages =	 {195--201},
  publisher =	 {CSLI Press},
  year =	 1996,
  address =	 {Stanford}
}



@incollection{Karttunen79,
    Year = {1979},
    Title = {Conventional Implicature},
    Address = {New York},
    Editor = {Choon-Kyu Oh and David A. Dinneen},
    Pages = {1--56},
    Booktitle = {Syntax and Semantics},
    Publisher = {Academic Press},
    Author = {Karttunen, Lauri and Stanley Peters},
    Volume = {11: Presupposition}
}


@Book{geurts99:_presup_pronoun,
  author =	 {Bart Geurts},
  title = 	 {Presuppositions and Pronouns},
  publisher = 	 {Elsevier},
  year = 	 1999,
  address =	 {Oxford}
}

@PhdThesis{schiehlen99:_seman,
  author = 	 {Michael Schiehlen},
  title = 	 {Semantikkonstruktion},
  school = 	 {Universit{\"a}t Stuttgart},
  year = 	 1999
}

@InProceedings{heim83,
  author = 	 {Irene Heim},
  title = 	 {On the projection problem for presuppositions},
  booktitle =	 {Second Annual West Coast Conference on Formal Linguistics},
  pages =	 {114--126},
  year =	 1983,
  editor =	 {M. Barlow and D. Flickinger and M. Westcoat},
  address =	 {Stanford}
}

@InCollection{blackburn01:_infer_comput_seman,
  author = 	 {Patrick Blackburn and Johan Bos and Michael Kohlhase and Hans de Nivelle},
  title = 	 {Inference and Computational Semantics},
  booktitle = 	 {Computing Meaning, Volume 2},
  pages =	 {11--28},
  publisher =	 {Kluwer Academic Publishers},
  year =	 2001,
  editor =	 {H. Bunt and R. Muskens and E. Thijsse}
}

@InCollection{beaver97:_presup,
  author = 	 {David Beaver},
  title = 	 {Presupposition},
  booktitle = 	 {Handbook of Logic and Language},
  pages =	 {939--1008},
  publisher =	 {Elsevier},
  year =	 1997,
  editor =	 {Johan van Benthem and Alice ter Meulen}
}

@InProceedings{KolTha05b, 
   author = {Alexander Koller and Stefan Thater}, 
   title  = {The Evolution of Dominance Constraint Solvers}, 
   year   = 2005, 
   booktitle = {Proceedings of the ACL-05 Workshop on Software}, 
   address = {Ann Arbor} 
} 

@PhdThesis{Koller04, 
   author = {Alexander Koller}, 
   title  = {Constraint-based and graph-based resolution of 
             ambiguities in natural language}, 
   year   = 2004, 
   school = {Universit{\"a}t des Saarlandes} 
} 


@InProceedings{FliKolTha05, 
   author = {Dan Flickinger and Alexander Koller and Stefan Thater}, 
   title  = {A new well-formedness criterion for semantics 
             debugging}, 
   year   = 2005, 
   booktitle = {Proceedings of the 12th International Conference on 
             HPSG}, 
   address = {Lisbon} 
} 


@InProceedings{koller06:_towar,
  author = 	 {Alexander Koller and Stefan Thater},
  title = 	 {Towards a redundancy elimination algorithm for underspecified descriptions},
  booktitle = 	 {Proceedings of the 5th Workshop on Inference in Computational Semantics},
  year =	 2006,
  address =	 {Buxton, England}
}


@Book{blackburn05:_repres_infer_natur_languag,
  author =	 {Patrick Blackburn and Johan Bos},
  title = 	 {Representation and Inference for Natural Language: {A} First Course in Computational Semantics},
  publisher = 	 {CSLI Publications},
  year = 	 2005
}

@InProceedings{koller06,
  author = 	 {Alexander Koller and Stefan Thater},
  title = 	 {An improved redundancy elimination algorithm for underspecified descriptions},
  booktitle = 	 {Proceedings of the 44th ACL/21st COLING},
  year =	 2006,
  address =	 {Sydney}
}

